package com.xb.Validate_Stack_Sequences_946;

import org.junit.Test;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;

/**
 * 给定pushed和popped两个序列，每个序列中的 值都不重复，只有当它们可能是在最初空栈上进行的推入 push
 * 和弹出 pop 操作序列的结果时，返回 true；否则，返回 false。
 *
 * 这个就是验证栈的出栈是否是正确的
 */
public class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        //参数说明 pushed 入栈的初始值 popped 出栈的顺序
        if (pushed.length<=1){
            return true;
        }
        Deque<Integer> stack = new ArrayDeque<>();
        //定义一个下标用来标记popped的小标
        int j = 0;
        for (int k : pushed) {
            stack.push(k);
            while (!stack.isEmpty() && stack.peek() == popped[j]) {
                j++;
                stack.pop();
            }
        }
        return stack.isEmpty();
    }
    public boolean validateStackSequences2(int[] pushed, int[] popped) {
        /**
         * 解法二：就是复用这个数组的值pushed数组里面的要插入的值
         * 首先通过遍历来找到popped第一个值中的和pushed相等的值
         * 就比如pushed是{1,2,3,4,5} 而popped是{4,5,3,2,1};
         * 通过循环遍历poppedIndex的值不动 动pushedIndex的值 直到找到第4个位置和pushed的位置和poppedIndex的第一个位置相等
         * top的值是用来干什么的 是用来作为pushed的移动的，做一个辅助指针
         *
         * 第一次找到位置相等的时候就直接两个都后移一个，这个时候就到了pushIndex = 4    poppedIndex = 1
         * 两个值是相等的，那么pushIndex = 6 poppedIndex = 2
         * top是用来记录一开始的前一个位置，为什么是这样呢？因为在第一次查找的时候，在第一个元素出队的时候，无论什么情况都可以正常出队
         * 所以pushIndex后面的都不用管只需要来管top前面的 然后再慢慢的对比top前面的和他预先的数组一个个遍历是否相同就可以了
         */
        int top = -1;
        int pushedIndex = 0;
        int poppedIndex = 0;
        while (pushedIndex < pushed.length) {
            if (pushed[pushedIndex] == popped[poppedIndex]) {
                pushedIndex++;
                poppedIndex++;
                while (top != -1 && pushed[top] == popped[poppedIndex]) {
                    top--;
                    poppedIndex++;
                }
            } else {
                pushed[++top] = pushed[pushedIndex++];
            }
        }
        return top == -1;
    }
    @Test
    public void test(){
        int[] pushed = {1,2,3,4,5};
        int[] popped = {4,5,3,2,1};
        new Solution().validateStackSequences2(pushed,popped);
    }
}
